This invention relates generally to computing devices, and, more particularly to data communication systems comprising such devices. Even more particularly, the present invention relates to integrated circuit design using Gray Code within such communication systems.
Communication systems are known to support wireless and wire-lined communications between wireless and/or wire-lined communication devices. Such communication systems range from national and/or international cellular telephone systems to the Internet to point-to-point in-home wireless networks. Each type of communication system is constructed, and hence operates, in accordance with one or more communication standards. For instance, wireless communication systems may operate in accordance with one or more standards including, but not limited to, IEEE 802.11, Bluetooth, advanced mobile phone services (AMPS), digital AMPS, global system for mobile communications (GSM), code division multiple access (CDMA), local multi-point distribution systems (LMDS), multi-channel-multi-point distribution systems (MMDS), and/or variations thereof.
Depending on the type of wireless communication system, a wireless communication device, such as a cellular telephone, two-way radio, personal digital assistant (PDA), personal computer (PC), laptop computer, home entertainment equipment, et cetera, communicates directly or indirectly with other wireless communication devices. For direct communications (also known as point-to-point communications), the participating wireless communication devices tune their receivers and transmitters to the same channel or multiple channels (e.g., one or more of the plurality of radio frequency (RF) carriers of the wireless communication system) and communicate over that channel or channels. For indirect wireless communications, each wireless communication device communicates directly with an associated base station (e.g., for cellular services) and/or an associated access point (e.g., for an in-home or in-building wireless network) via an assigned channel, or channels. To complete a communication connection between the wireless communication devices, the associated base stations and/or associated access points communicate with each other directly, via a system controller, via the public switch telephone network, via the internet, and/or via some other wide area network.
For each wireless communication device to participate in wireless communications, it includes a built-in radio transceiver (i.e., receiver and transmitter) or is coupled to an associated radio transceiver (e.g., a station for in-home and/or in-building wireless communication networks, RF modem, etc.). As is known, the receiver receives RF signals, demodulates the RF carrier frequency from the RF signals to produce baseband signals, and demodulates the baseband signals in accordance with a particular wireless communication standard to recapture the transmitted data. The receiver is coupled to an antenna and includes a low noise amplifier, one or more intermediate frequency stages, a filtering stage, and a data recovery stage. The low noise amplifier receives inbound RF signals via the antenna and amplifies them. The one or more intermediate frequency stages mix the amplified RF signals with one or more local oscillations to convert the amplified RF signals into the baseband signals or intermediate frequency (IF) signals. The filtering stage filters the baseband signals or the IF signals to attenuate unwanted out-of-band signals to produce filtered signals. The data recovery stage recovers raw data from the filtered signals in accordance with the particular wireless communication standard.
As is also known, the transmitter converts data into RF signals by modulating the data to produce baseband signals and mixing the baseband signals with an RF carrier to produce RF signals. The transmitter includes a data modulation stage, one or more intermediate frequency stages, and a power amplifier. The data modulation stage converts the raw data into baseband signals in accordance with a particular wireless communication standard. The one or more intermediate frequency stages mix the baseband signals with one or more local oscillations to produce the RF signals. The power amplifier amplifies the RF signals prior to transmission via the antenna.
Further, data transmissions are serial streams of data, but within a network component (e.g., switch, relay, bridge, gateway, et cetera) the data is processed in parallel. It is a function of the transceiver within each communication device or network component to convert data from a serial to a parallel form, or vice-versa. In general, the transmitter converts parallel data into serial data and sources the serial data onto a communications link. A receiver receives serial data via a communications link and converts it into parallel data. A critical function of the receiver is to accurately sample the received serial data to be able to produce the parallel data.
As communication systems have become more advanced, and as their data capacity has increased, buffering of incoming and outgoing data has become essential. Buffering of data allows a host device to attend to other tasks on a time-multiplexed basis during a communications session. For example, buffering is used to hold multiple communication sessions simultaneously, to perform signal modulation and demodulation and to perform error correction. In addition, buffering can facilitate asynchronous communications, making it unnecessary for communication devices to share a common time base.
Buffering is commonly accomplished using RAM-based FIFOs. A FIFO is a first-in-first-out (FIFO) device in which data is temporarily stored in random-access memory (RAM). When a suitable unit, e.g., a byte, of data is received by the FIFO, the data unit is stored at a FIFO address indicated by a write pointer. Once that data is stored, the write pointer is incremented to the next FIFO address, which is where the next unit of received data will be stored. When a device is ready to read from the FIFO, it reads from a FIFO address indicated by a read pointer. After the data is read, the read pointer is incremented so that the next read is from the next FIFO address. Each pointer is basically a counter that counts data transfers. The counters are modulo in that they wrap to zero when a maximum count is reached.
Counters are used extensively in the design of integrated circuits. For example, conventional binary-code counters can be used as FIFO pointers. Binary counter design is mature enough that, by entering a few specifications (such as the counter range and speed), a computer can provide an optimized counter design. With a binary counter, however, there can be many bit differences in the representation of two adjacent binary numbers. A disadvantage of binary counters, therefore, is that there can be considerable ambiguity when a count is read during a count transition. For example, when a count increments from 011=3 to 100=4, every bit value changes. However, the changes can take place at slightly different times across the bit positions. If the count is used in the same clock domain, this is nota big problem. However, when the count is used in more than one clock domain (e.g., in an asynchronous circuit design), ambiguity can result as to the correct count.
For example, in a RAM-based asynchronous FIFO, the status of the FIFO (i.e., whether a data unit is present in the FIFO) is determined by comparing the read pointer and the write pointer. However, because the read pointer and the write pointer are in different clock domains, direct comparison will not generate a reliable result. For example, when the count increments from 011=3 to 100=4, any of eight possible 3-bit binary values might be read during the transition. This simultaneous transition of a large number of bits can increase the risk of transition errors and can increase the electrical noise generated by the circuitry. Attempts to design around such extreme ambiguities can add considerable complexity to the counter or to circuit elements that respond to the counter.
To avoid the problems with binary counters, xe2x80x9cGray Codexe2x80x9d counters are often used. Gray code is an alternative to binary code that requires a change in only one bit position between adjacent numbers. An example 3-bit Gray-code sequence can be: 0=000, 1=001, 2=011, 3=010, 4=110, 5=111, 6=101, and 7=100. Incrementing the last value, 100, yields the first value 000. Since only one bit position changes during a unit increment, the only possible reads during a transition are the value being changed from and the value being changed to. It is much easier to design around this limited ambiguity than it is to design around the much more extensive ambiguities associated with binary counter reads. Further, in an asynchronous circuit, a Gray-code counter""s count can be transferred among the different clock domains without the noise and transition errors of a binary counter.
While Gray-codes are well known in the art and can be readily constructed for any bit length, Gray-code counters are more complex and difficult to design. Further, Gray-code counters are not readily scaled. Some prior art solutions addressing these problems exist. For example, a typical prior art Gray-code counter comprises a count register for storing a Gray-code value, a Gray-to-binary code translator for converting the stored Gray-code value to a corresponding binary-code value, a binary-code incrementer for incrementing the binary-code value, and a binary-Gray-code translator for converting the incremented binary-code value to the corresponding Gray-code value. However, another limitation of Gray-code is that it requires an integer depth that is a power of two. Thus, a disadvantage of prior art Gray-code counters is that, when the target FIFO depth is not a power of two, the FIFO design has excess capacity. For example, when a communications application only requires a FIFO depth of 78, the power-of-two limitation requires the use of a 128-address FIFO.
In contrast, binary-code counters can be designed for any positive integer depth. The discrepancy between target and Gray-code-imposed capacities can be much greater for larger FIFOs, resulting in the inability to use a prior art Gray-code counter because of size and/or costs constraints in terms of integrated circuit area and because an oversized FIFO may be too slow for the particular application.
Some prior art solutions to these problems do exist. These solutions comprise skipping certain binary values while maintaining the Gray-code nature of the count. However, a very complex algorithm is used in these prior art solutions to determine which binary values to skip. These solutions thus require a computer and associated software to run the algorithm and determine the Gray-code pattern for a given modulo number. For especially large modulo numbers (FIFO size), the Gray-code pattern will have to be stored on the integrated circuit for rapid access. Further, when determining the FIFO status, the counter data must be transformed from a Gray-code pattern, to a binary pattern, and back to a Gray-code pattern. Having to perform the complex algorithm twice involves a heavy cost in time and efficiency.
Therefore, a need exists for a Gray-code counter and a binary incrementer-decrementer algorithm therefore that can reduce or eliminate the complexity and efficiency problems associated with the prior art.
The embodiments of the non-power-of-two modulo N Gray-code counter (the xe2x80x9cGray-code counterxe2x80x9d) and binary incrementer-decrementer algorithm of the present invention substantially meet these needs and others. One embodiment of the Gray-code counter of this invention comprises a Gray-to-binary converter for receiving an M-bit Gray-code input value and converting the M-bit Gray-code input value to an M-bit binary-code input value, IB[mxe2x88x921:0]; a binary incrementer-decrementer for converting the M-bit binary-code input value to an M-bit binary-code output value, OB[mxe2x88x921:0], wherein the M-bit binary-code output value will differ from the M-bit binary-code input value by modulo +/xe2x88x921 for all but one value of the M-bit binary-code input value; a binary-to-Gray converter for converting the M-bit binary-code output value to an M-bit Gray-code output value; and a clocked storage device operably coupled to the binary-to-Gray converter for storing the M-bit Gray-code output value and for providing the M-bit Gray-code output value to the Gray-to-binary converter as a next M-bit Gray-code input value.
The binary incrementer-decrementer further comprises an incrementer-decrementer algorithm for skipping certain binary values in order to maintain the Gray-code nature of the counter when translated to Gray-code, while allowing the Gray-code counter to be implemented as a modulo counter of any even size. The modulo N value is thus an even whole number equal to the range of the binary incrementer-decrementer. In one embodiment of the Gray-code counter of this invention, converting the M-bit binary-code input value IB[mxe2x88x921:0] to an M-bit binary-code output value, OB[mxe2x88x921:0], comprises incrementing the M-bit binary-code input value according to the logic algorithm:
IF IB[mxe2x88x921:0]=2Mxe2x88x921+N/2xe2x88x921, THEN
OB[mxe2x88x921:0]=2Mxe2x88x921N/2
ELSE
OB[mxe2x88x921:0]=IB[mxe2x88x921:0]+1,
wherein N less than =2M.
This embodiment""s corresponding decrementing algorithm for converting the M-bit binary-code input value IB[mxe2x88x921:0] to a decremented M-bit binary-code output value, OB[mxe2x88x921:0], comprises decrementing the M-bit binary-code input value according to the logic algorithm:
IF IB[mxe2x88x921:0]=2Mxe2x88x921xe2x88x92N/2, THEN
OB[mxe2x88x921:0]=2Mxe2x88x921+N/2xe2x88x921
xe2x80x83ELSE
OB[mxe2x88x921:0]=IB[mxe2x88x921:0]xe2x88x921,
wherein N less than =2M.
Further embodiments of the binary incrementer/decrementer algorithm of this invention exist and are discussed below as part of the detailed description of the invention.
The bus width, M, in bits used to represent the Gray-code in the embodiments of the present invention is obtained by determining a value of 2M that is greater than or equal to N, where M is a positive whole value. The preferred value of M is typically obtained by using the smallest value of 2M that is greater than or equal to N. Prior art Gray-code, and Gray-code counters, require an integer depth that is a power of two, i.e., 2M. Gray-code counters designed in accordance with the teachings of this invention, however, can be of any even size and, in particular, of any even non-power-of-two size due to the binary incrementer-decrementer algorithm disclosed herein.
The clocked storage device can be a register comprising a plurality of D-type flip-flops. In particular, the number of D-type flip-flops can be equal to M, resulting in one flip-flop per bit of a Gray-code value.
Other embodiments of the present invention include a method for operating a Gray-code counter designed in accordance with the teachings of this invention and a method for generating a modulo Gray-code representation of a non-power-of-two set of binary values. The various embodiments of the present invention can be implemented within a communications device, for example, as a counter for a communications buffering circuit. Further uses for a Gray-code counter designed in accordance with the teachings of this invention will be known to those familiar with the art.